q21_what_is_the_cause_of_internet_rush_hourfandomcom-20200213-history
Q21: What is the cause of internet rush hour? Wiki
Short Answer You come home after a long day of work, sit down at your computer, and a popular youtube video shows up on your home page. You click on the video out of curiosity, and it begins to load. The first 10 seconds stream perfectly, and then the video needs to buffer and it continues to buffer, buffer, and buffer. This happens intermittently every 10 seconds or so until you become frustrated and try another video only to have the same problem. You try another popular website, and it’s the same story. So what’s really going on, and why can’t you just enjoy a couple of videos after a long day at work? The obvious reason is that the rest of the world is also home from work, and also trying to access the same popular videos; sharing scare resources among a pool of data hungry users inevitably leads to some waiting in line. A similar story could be said for customers at a bank. One person may go to the bank on their lunch break in hopes of making a quick deposit only to find out that many other people also went to the bank on their lunch break. Now a line has formed and almost everyone is waiting to be served. There are difference performance metrics for networks such as throughput and delay. Throughput is measured by the data rate (bps) and can be significantly reduced by protocol overheads. Delay takes many forms such as transmission delay (time for a transmitter to send all bits of a packet), propagation delay (time for one bit to transmit from source to destination), and processing delay (time required to process packets at the source, routers or destination). There is another form of delay known as queueing delay that is the subject of this Wiki article. Queueing delays are a significant component in the performance of communication networks. In a network where resources are shared (almost all communication networks we use today) performance generally deteriorates as demand moves toward capacity. Why do we Model Queueing Delay? Congestion arises when the number of packets being transferred through a network exceeds the packet handling capacity of the network. A queue will grow as long as the arrival rate continues to exceed the transmission rate. Network delay increases as a queue grows larger; because queues have finite capacity, packets can be dropped. This is the worst case scenario for everyone. When a packet arrives at a router, it is stored at an input buffer where it waits in line to be served. Being served typically involves a routing decision being made. Once a packet has been served and a decision has been made as to where to send it, the packet moves to an appropriate output buffer where it waits in line to be transmitted. Two general scenarios can therefore cause congestion and queuing delay: when packets arrive to fast to be routed and the input buffers begin to fill; or if the packets arrive faster than can be transmitted, and the output buffers begin to fill. During peak internet hours some nodes in a network may reach capacity, causing packets to get discarded. This in turn leads to rerouting and congestion control messaging within the network which induces overhead. The extra overhead causes more buffers to overflow, and the retransmission of discarded packets causes even heavier traffic. As delays continue to increase, even successfully delivered packets are retransmitted due to timeout. Therefore, queueing delay can have a significant snowball effect. There are different ways to reduce congestion. For instance a source can detect forms of congestion such as delay and then adjust its transmission flow as necessary. Networks use many flow control mechanisms to control congestion caused by queuing delay. One example of flow control could be hop by hop: If one node becomes congested, it could send a message to other neighboring nodes asking them to throttle there flow of packets; those neighbors would begin to induce larger queues, and in turn would signal to their neighbors to send less packets. This behavior propogates back to the source transmitting the packets, and is known as Backpressure. It is used in connection oriented networks that allow it. Modeling queueing delay in networks allows for a deeper insight into why congestion occurs. An understanding of queuing systems, and the ability to model queuing systems, is necessary to better understanding such phenomona. Better insight can aid in avoiding congestion induced queueing delay, and can help in fine tuning of AQM (active queue management schemes) schemes. A Queueing System Model A diagram of a queueing system model, and also the elements that comprise a queueing system are shown below. Users arrive from some population to the system at random times S1, S2, S3,....,Si. Si denotes the arrival time of the ith customer. N(t) is the number of users in the system at time t. Nq(t) is the number of users in queue at time t. Wq is the waiting time in queue. Ns(t) is the number of users in service at time t. Ts is the service time. T is the total time in the system. The customer arrival rate is denoted by λ. The ith user arrives at the system requesting a service that will last Ts seconds of service time from one server. If all the servers are in used, then the arriving user joins a queue where he remains until a server become available. Kendall's Notation A/S/''c''/''K''/''N''/D *A denotes the arrival process to the queue *S denotes the service time distribution *c indicates the number of servers *K is the maximum number of users allowed in the system at any time *N indicates the size of the population of users *D denotes the queueing discipline Poisson Distribution Many queueing systems, including the M/M/1 queueing system, assume a Poisson arrival process. This is a very good approximation for systems in which the number of users is very large, the number of arrivals occur with a known average rate, and every users decision to use the system is independent of every other user. The pmf for the Poisson random variable is given by: {PX=k=p_{X}(k)=\frac{\lambda t }{k!}e^{-\lambda t }} * {k} is the number of packet arrivals observed in the time interval {t} . * {\lambda} is the average arrival rate in packets/second Exponential Distribution Service times in a queueing system are often modeled as iid exponential random variables. The pdf of an exponential distribution is given by: {f(x;\mu )=\left\{\begin{matrix} \mu e^{-\mu x},&x\geq 0, \\ 0,&x< 0. \end{matrix}\right.} * {1/\mu} is the average duration of the exponetial service * {\mu} is the average number of completed services per time unit Modeling service times by an exponential distribution means that, with high probability, a user will occupy a server for a short time. It also means that, with a low probability, a user will occupy a server for a long time. In modeling telephone queuries this is a very reasonable assumption; that is, it is reasonable to assume that most phone calls are short in duration. In a packet based network, service time on a link is proportional to the message size. Therefore one may have to assume that packet lengths are exponentially distributed, which isn't always the case. Nevertheless, an exponential distribution is still a good starting point for modeling service times. Little's Theorem The average number of users (N) in a queuing system is given by the following equation: {N=\lambda T} λ is the average customer arrival rate and T is the average service time for a customer. Consider the example of a convenient store where the customer arrival rate (λ) doubles but the customers still spend the same amount of time (T) in the store. This will double the number of customers in the convenient store. Similarly, if the customer arrival rate remains the same but the customer service time (like the time waiting to cash out) doubles this will also double the number of customers in the store. M/M/1 Queue Description: This is the simplest queuing system to analyze. While a single server is much too small to accurately describe a single user’s interaction with the congestion of the internet, it forms the basis of the technical explanation of queuing theory. A more accurate system with multiple servers can be found in the advanced material. In the M/M/1 model, there is a single server servicing user requests. If a new user requests use of the server while it is busy, it must wait in a queue or a buffer until all the users that arrived before it are serviced. Then it must wait until the server finishes serving its request. At this point, this specific user will exit the system. This system is represented graphically below in Figure … . In this model, the arrival and service time are negative exponentially distributed (poisson process) and are both memory-less Markovian processes. This queuing system can be applied to a wide variety of every day situations. The parameters used to define this system are the arrival rate lambda and the service time, u. In this simple case, we assume that there is no maximum buffer size. The state space for this system is simply the set of users in the system, which is simply the set of non-negative integers. The system will change from the current state (state i) when another user arrives (new state of i+1) or when a user is done being serviced (new state of i-1). If a user enters the system in the same time frame that a user is done being serviced, the state will remain the same. The resulting probability transition matrix for this system can be seen below in Figure… . Figure … represents the non-negative integer state space of the system along with the transition probabilities. Figure... : An Example M/M/1 Queuing Node Figure ... : Probability Transition Matrix for M/M/1 Queue Figure ... : Graphical State Space and Transition Probabilitites for M/M/1 Queue Mathematical Analysis The most important system characteristic to analyze is the stability. A system is considered stable if the rate at which users are serviced is faster than the rate at which they arrive. If this condition is not upheld, the queue length will grow indefinitely over time, causing an infinite amount of delay for each new user. We set ρ=lambda/u and check that it is less than 1. ρ also represents the average proportion of time the server is in use. Therefore, a low ρ value implies that the server resources are being wasted while idling until the next user arrives. Since u is the number of users serviced during a certain time slot, Ts=1/u is the amount of time on average required to service a single user. By using the distribution models of lambda and u, we are able to determine the probability that the system is in state i(Source:Harrison, Peter). From there, with knowledge of Ts and ρ, we can mathematically determine many other useful characteristics of the system. The probability that the system is in state i is πi = (1- ρ)*ρi , where ρ = lambda/u Expected number of users in the system Ns = Sum(j*P= j,j = 0,inf) = ρ/(1-ρ) Average time a customer spends in the system Ws = Ts/(1- ρ) Average number of customers waiting in the queue Nq = ρ*Ns= ρ2/(1- ρ) Average time a customer spends waiting in the queue Wq = Ws*ρ= ρ*Ts/(1- ρ) Probability of more than k customers in the system Pk = (ρ)k+1 Advanced Material: M/M/c Queues Description M/M/c queue model generalizes all of the analysis done on the M/M/1 queue to systems with an arbitrary number of servers. The arrivals still occur according to a Poisson distrubution at a rate of lambda and still have service time with exponential distribution u. The state space of the system remains the same, however the transistional probability matrix will change. This is due to the fact that the additional servers enable the system to service multiple users simultaneously. The transition to state i+1 remains the same due to the unchanged arrival distribution. However, the transition to lower states and probability of staying in the same state now depends on the number of servers. Figure ... shows a graphical representation of the M/M/c transition proabability matrix. It is interesting to note that the matrix has two differenct cases: the first case where the number of users in the system Ns is less than the number of servers c and the other case where Ns>c. In the first case, every user in the system is being serviced simultaneously. Having additional servers obviously increases the capacity of the system to handle a larger number of users before becoming unstable. The new modeling equations are as follows: System utility ρ = λ/(c*u) Probability of system being in state i based on Erlang's Formula (Source:Kleinrock, Leonard ) Expected number of users in the system Figure ... : M/M/c Transitional Probability Matrix Examples Example 1: Poisson Distribution Here is the example for this Example 2: Comparing Various M/M/1 and M/M/2 Systems Suppose we have a grocery store where customers arrive at the check out line with a Poisson distribution at a mean rate of 0.5 customers per minute. The cashier is able to ring out customers at an exponential rate, with an average of 4 customers per minute. This cashier is the only one working during this particular shift. 1) Determine (i) the utility of the system, (ii) the expected number of customers in the system, (iii) the average number of customers in line, (iv) the average time the customer is in the system, (v) the average waiting time, (vi) the probability of being checked out immediately and (vii) the probability of having 2 people in line when a customer tries to check out. 2) Then determine parts i-v if a different cashier was working who was able to ring up customers at an exponential rate with an average of 8 customers per minute. 3) Then calculate parts i-vii if instead they had an additional cashier working, both of whom averaged 4 customers per minute. Compare the results. Answer: 1) λ = 0.5 customers/min u = 4 customers/min c = 1 i) ρ = λ/u = 0.5/4 = 0.125 ii) Ns = ρ/(1-ρ) = 0.125/(1-0.125) = 0.1429 customers iii) Nq = ρ*ρ/(1-ρ) = 0.125*0.125/(1-0.125) = 0.179 customers iv) Ws = Ts/(1-ρ) = 0.25/(1-0.125) = 0.2857 mins v) Wq = ρ*Ts/(1-ρ) = 0.125*0.25/(1-0.125) = 0.0357 min vi) P(Ns = 0) = 1-ρ = 1-0.125 = 87.5% vii) P(Nq = 2) = (1-ρ)*ρ^n = (1-0.125)*0.125^2 = 1.36% 2) λ = 0.5 customers/min u = 8 customers/min c = 1 i) ρ = λ/u = 0.5/8 = 0.0625 ii) Ns = ρ/(1-ρ) = 0.0625/(1-0.0625) = 0.1667 customers iii) Nq = ρ*ρ/(1-ρ) = 0.0625*0.0625/(1-0.0625) = 0.00416 customers iv) Ws = Ts/(1-ρ) = 0.125/(1-0.0625) = 0.133 mins v) Wq = ρ*Ts/(1-ρ) = 0.0625*0.125/(1-0.0625) = 0.00833 min vi) P(Ns = 0) = 1-ρ = 1-0.0625 = 93.75% vii) P(Nq = 2) = (1-ρ)*ρ^n = (1-0.0625)*0.0625^2 = 0.366% 3) λ = 0.5 customers/min u = 4 customers/min c = 2 i) ρ = λ/(c*u) = 0.5/(2*4) = 0.0625 We also must calculate π0 using Erlang's formula π0 = (1-K)/(1-ρ*K), where K = A/B and A = sum(c*ρ)^i/i! for all i and B = sum(c*ρ)^i/i! for all i<=c A = (2*0.0625)^0/0! + (2*0.0625)^1/1! = 1+0.125 = 1.125B = (2*0.0625)^0/0! + (2*0.0625)^1/1! + (2*0.0625)^2/2! = 1+0.125+ 0.0078 = 1.132so K = A/B = 1.125/1.132 = 0.993π0 = (1-K)/(1-ρ*K) = (1-0.993)/(1-0.625*0.993) = 0.00731 ii) Ns = π0*ρ/(1-ρ)+c*ρ = 0.00731*0.0625/(1-0.0625)+2*0.0625 = 0.1255 customers iii) Nq = π0*ρ/(1-ρ) = 0.00731*0.0625/(1-0.0625) = 0.0005 customers iv) Ws = Wq+Ts = 0.00097+0.25 = 0.25097 mins v) Wq = π0/c*Ts/(1-ρ) = 0.00731/2*0.25/(1-0.0625) = 0.00097 min As expected, the single initial cashier resulted in the longest time in store and longest wait in line. Also, unsurprisingly, there was an smalled expected time waiting in line to be checked in out in the model with two cashiers (part 3). The most interesting comparison is between the overall time in the system between parts 2 and 3. This particular example suggests that there is a shorter expected overall time in the grocery store if there is a single cashier working twice as fast as average compared to two cashiers operating at an average rate. References Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley. pp. 172–173. Alberto Leon-Garcia, “Probability, Statistics, and Random Processes for Electrical Engineering" Kleinrock, Leonard (1975). Queueing Systems Volume 1: Theory. pp. 101–103,404. ISBN 0471491101. Barbeau, Michel; Kranakis, Evangelos (2007). Principles of Ad-hoc Networking. John Wiley & Sons. p. 42. ISBN 0470032901. (1) Latest activity Photos and videos are a great way to add visuals to your wiki. Find videos about your topic by exploring Wikia's Video Library.